package com.zzy.algorithm.sort;

import com.zzy.algorithm.model.PrintArray;

public class Q31_HeapSort {

    public static int[] nums = new int[]{5,7,1,2,8,9,3};

    public static void main(String[] args) {
        Q31_HeapSort q31_heapSort = new Q31_HeapSort();
        q31_heapSort.heapSort(nums);
        PrintArray.print(nums);
    }

    private void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    private void heapSort(int[] nums){
        int len = nums.length;
        buildMaxHeap(nums);
        while (len > 0){
            swap(nums,0,len - 1);
            len--;
            adjustHeap(nums,0,len);
        }
    }

    private void buildMaxHeap(int[] nums){
        int len = nums.length;
        for(int i = len / 2 - 1; i>=0 ;i--){
            adjustHeap(nums,i,len);
        }
    }

    private void adjustHeap(int[] nums,int i,int len){
        int maxIndex = i;
        int left = (i << 1) + 1;
        int right = (i << 1) + 2;
        if(left < len && nums[left] > nums[maxIndex]){
            maxIndex = left;
        }
        if(right < len && nums[right] > nums[maxIndex] && nums[left] < nums[right]){
            maxIndex = right;
        }
        if(i != maxIndex){
            swap(nums,i,maxIndex);
            adjustHeap(nums,maxIndex,len);
        }
    }



//    private void swap(int[] nums,int i,int j){
//        int tmp = nums[i];
//        nums[i] = nums[j];
//        nums[j] = tmp;
//    }
//
//    private void heapSort(int[] nums){
//        int len = nums.length;
//        buildMaxHeap(nums);
//        while(len > 0){
//            swap(nums,0,len - 1);
//            len--;
//            adjustHeap(nums,0,len);
//        }
//    }
//
//
//    private void buildMaxHeap(int[] nums){
//        int len = nums.length;
//        for(int i = len / 2 - 1 ;i >= 0 ; i--){
//            adjustHeap(nums,i,len);
//        }
//    }
//
//    private void adjustHeap(int[] nums,int i,int len){
//        int maxIndex = i;
//        int left = 2 * i + 1;
//        int right = 2 * i + 2;
//        if(left < len && nums[left] > nums[maxIndex]){
//            maxIndex = left;
//        }
//        if(right < len && nums[right] > nums[maxIndex] && nums[right] > nums[left]){
//            maxIndex = right;
//        }
//        if(i != maxIndex){
//            swap(nums,i,maxIndex);
//            adjustHeap(nums,maxIndex,len);
//        }
//    }

}
